// 给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。

// 给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/predict-the-winner
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

// 动态规划
var PredictTheWinner = function (nums) {
    let dp = nums.map(e => e)
    for (let i = nums.length - 2; i >= 0; i--) {
        for (let j = i + 1; j < nums.length; j++) {
            dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
        }
    }
    console.log(dp)
    return dp[nums.length - 1] >= 0;
};

// 递归
var PredictTheWinner = function (nums) {
  let pick = function (i, j) {
      if (i == j) {
          return nums[i]
      }
      const pickI = nums[i] - pick(i + 1, j)
      const pickJ = nums[j] - pick(i, j - 1)
      return Math.max(pickI, pickJ)
  }
  return pick(0, nums.length - 1) >= 0
}